package net.obsearch.example.lev;

public class Lev {
	public static int distance(short[] s, short[] t)  {
		return distance(convert(s) , convert (t));
	}
	
	private static  int[] convert(short[] s){
		int[] res = new int[s.length];
		int i = 0;
		for(short k : s){
			res[i] = k;
			i++;
		}
		return res;
	}
	
	
	public static int distance(int[] s, int[] t)  {
		
		int d[][];
	    int n; 
	    int m;
	    int i; 
	    int j; 
	    int s_i;
	    int t_j;
	    int cost; 
	   

	      n = s.length;
	      m = t.length;
	      if (n == 0) {
	        return (short)m;
	      }
	      if (m == 0) {
	        return (short)n;
	      }
	      d = new int[n+1][m+1];


	      for (i = 0; i <= n; i++) {
	        d[i][0] = i;
	      }

	      for (j = 0; j <= m; j++) {
	        d[0][j] = j;
	      }


	      for (i = 1; i <= n; i++) {

	        s_i = s[i - 1];

	        for (j = 1; j <= m; j++) {

	          t_j = t[j - 1];


	          if (s_i == t_j) {
	            cost = 0; 
	          }           
	          else {
	            cost = 1;
	          }


	          d[i][j] = min (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);

	        }

	      }


	      return d[n][m];
	}
	
	private static int min (int a, int b, int c) {
        int mi;

          mi = a;
          if (b < mi) {
            mi = b;
          }
          if (c < mi) {
            mi = c;
          }
          return mi;

        }

}
